package me.timlong.sort;

public class InsertSort {

    // Definition for singly-linked list.
    private class ListNode {
        int val;
        ListNode next;
        ListNode(int x) {
            val = x;
            next = null;
        }
    }

    /**
     * 题目描述
     * 使用插入排序对链表进行排序。
     * Sort a linked list using insertion sort.
     *
     * 解决思路：
     * 考虑到链表的结构：插入排序的结构应该从头节点开始，
     * 搜索从头节点开始第一个大于当前遍历所在的节点并进行插入
     *
     *
     * @param head
     */

    public ListNode insertionSortList(ListNode head) {
        if(null == head || null == head.next)
            return head;

        // 虚拟节点head0
        ListNode head0 = new ListNode(0);

        ListNode pre;
        ListNode curr = head;
        ListNode nxt = curr.next;

        while (null != curr){
            pre = head0;
            // 保存遍历的当前节点的next
            ListNode curr_next = curr.next;

            // 从头开始找val，直到curr应该插在pre 与 pre.next之间
            while(pre.next != null && pre.next.val < curr.val)
                pre = pre.next;

            //curr插在之间

            curr.next = pre.next;
            pre.next = curr;

            // 无须保持后面链表与前面排完序的序列相连，curr后挪
            curr = curr_next;
        }

        return head0.next;


    }

    public static void main(String[] args) {

    }


}
